To quickly specify a point of QoS degradation in a communication network at the time of QoS degradation, a number of monitoring devices are arranged in the network to always monitor the QoS in their places. When QoS degradation has occurred, the section of the QoS degradation is estimated based on the position of the monitoring device where the QoS degradation has occurred (e.g., Japanese Patent Laid-Open No. 2002-271392). This method requires a number of monitoring devices to accurately estimate the QoS degradation point, and the arrangement cost is high. To solve this problem, a method has been proposed which estimates a QoS degradation point based on the QoS information and routing information of each communication flow that passes through a network (e.g., Japanese Patent Laid-Open No. 2006-238052).
The QoS degradation point estimation method disclosed in Japanese Patent Laid-Open No. 2006-238052 will be described. First, a table (to be referred to as a flow link table hereinafter) is created, which associates a flow, links (directed links) the flow passes through, and QoS with each other. Assume that flows F1 to F5 go through a network including routers (or packet switches) R1 to R6 shown in FIG. 15. In the network illustrated in FIG. 15, each link is named as shown in FIG. 16. A packet loss rate is used to express QoS. The packet loss rates of the flows F1 to F5 are assumed to be 3.0%, 2.5%, 3.5%, 1.0%, and 0.5%, respectively. In this case, a flow link table shown in FIG. 17 is created. Assume that each flow transmits 100 packets per second, and the packet loss rate is calculated based on the number of lost packets for every 0.2 sec. A bit “1” in FIG. 17 indicates that a flow passes through a link.
The QoS degradation point estimation method next performs non-degraded link removal processing. More specifically, based on predetermined degradation threshold and non-degradation threshold of flow quality, each flow with quality poorer than the degradation threshold is defined as a degraded flow. Each flow with quality higher than the non-degradation threshold is defined as a non-degraded flow. The remaining flows are defined as intermediate quality flows. A reduced flow link table is created by removing, from the flow link table, the rows of the intermediate quality flows, the rows of the non-degraded flows, and the columns of links the non-degraded flows pass through.
For example, the degradation threshold is set to 2% in terms of the packet loss rate, and the non-degradation threshold to 1%. In the example shown in FIG. 17, F1 to F3 are degraded flows, F5 is a non-degraded flow, and F4 is an intermediate quality flow. The row of the intermediate quality flow F4, the row of the non-degraded flow F5, and the columns of links L30 and L45 the non-degraded flow F5 passes through are deleted from the flow link table shown in FIG. 17, as shown in FIG. 18, thereby creating a reduced flow link table shown in FIG. 19.
Finally, the QoS degradation point estimation method estimates a QoS degradation point based on the reduced flow link table in FIG. 19. In, e.g., an estimation method based on the number of QoS degradation flows, the numbers of degraded flows which pass through links L10, L20, L50, and L40 in FIG. 19 are 1, 3, 1, and 1, respectively. Hence, the link L20 through which a maximum number of flows pass is estimated as a QoS degradation point.
In a minimum link count estimation method, a set of flows that pass through the links L10, L20, L50, and L40 in FIG. 19 is considered. A set of a minimum number of links, which covers all flows in FIG. 19, is obtained as a degraded link set. More specifically, in the example shown in FIG. 19, the sets of flows passing through the links L10, L20, L50, and L40 are {F1}, {F1,F2,F3}, {F2}, and {F3}, respectively. A union of flows passing through, e.g., a link set {L10, L50, L40} including three links is {F1,F2,F3} which covers all flows. A link set {L10, L20} including two links or a link set {L20} including one link can also cover all flows. Of the link sets that cover all flows, {L20} including a minimum number of links is estimated as a minimum link set.